package algocasts;

import java.util.*;

public class P61_theSkylineProblem {
    public List<List<Integer>> getSkyline(int[][] buildings) {
        List<List<Integer>> res = new ArrayList<>();

        List<int[]> ps = new ArrayList<>();
        // 为了方便排序，对于左端点，令高度为负；对于右端点令高度为正
        for (int[] b : buildings) {
            ps.add(new int[]{b[0], -b[2]});
            ps.add(new int[]{b[1], b[2]});
        }
        // 先按照横坐标进行排序，如果横坐标相同，则按照左端点排序
        //             如果相同的左/右端点，则按照高度进行排序
        ps.sort((a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);

        // 大根堆
        Queue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        int preHeight = 0;
        pq.add(preHeight);
        for (int[] p : ps) {
            int point = p[0], height = p[1];
            if (height < 0) {
                // 如果是左端点，说明存在一条往右延伸的可记录的边，将高度存入优先队列
                pq.add(-height);
            } else {
                // 如果是右端点，说明这条边结束了，将当前高度从队列中移除
                pq.remove(height);
            }
            // 取出最高高度，如果当前不与前一矩形“上边”延展而来的那些边重合，则可以被记录
            int cur = pq.peek();
            if (cur != preHeight) {
                List<Integer> list = new ArrayList<>();
                list.add(point);
                list.add(cur);
                res.add(list);
                preHeight = cur;
            }
        }
        return res;
    }

    public List<int[]> skylineKeyPointMaxHeap(int[][] buildings) {
        List<int[]> result = new ArrayList<>();
        List<int[]> height = new ArrayList<>();
        for (int[] b : buildings) {
            height.add(new int[]{b[0], -b[2]});
            height.add(new int[]{b[0], b[2]});
        }
        height.sort((a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
        Queue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        pq.add(0);
        int preHeight = 0;
        for (int[] h : height) {
            if (h[1] < 0) pq.add(-h[1]);
            else pq.remove(h[1]);
            if (pq.peek() != preHeight) {
                result.add(new int[]{h[0], pq.peek()});
                preHeight = pq.peek();
            }
        }
        return result;
    }

}
